Data communication systems often use binary linear codes to offset the effect of noise. The ideal goal is to reach the Shannon limit of a communication channel. The Shannon limit is the highest rate of error-free transmission possible over a communication channel.
One class of codes that exhibit very good performance is low-density parity-check (LDPC) codes. Conventional decoders for LDPC codes are based on iterative belief-propagation (BP) decoding. An alternate decoding method is based on linear programming (LP), J. Feldman, M. J. Wainwright, and D. Karger, “Using linear programming to decoding binary linear codes,” IEEE Trans. Inform, Theory, 51:954-972, March 2005, incorporated herein by reference.
LP decoding has some attractive features. An LP decoder deterministically converges, and when the decoder converges to an integer solution, one knows that the optimal maximum likelihood (ML) codeword has been found. When LP decoding converses to a non-integer solution, a well-defined non-integer “pseudo codeword” has been found. Unfortunately, LP decoding is more complex than BP decoding. In the formulations originally described by Feldman et al., the number of constraints in the LP decoding problem grows exponentially with the maximum check node degree, and the resulting computational load can be prohibitive.
The very large computational burden of LP decoding has motivated the introduction of adaptive linear programming (ALP) decoding, M. H. Taghavi N. and P. H. Siegel, “Adaptive linear programming decoding,” In Proc. Int. Symp. Inform. Theory, pages 1374-1378, July 2006, incorporated herein by reference. Instead of starting with all of the LP constraints, they first solve for the LP optimum of a problem where the values of the binary codeword symbols are only constrained to be greater than zero and less than one. At the resulting optimum, for each check node, they determine the local constraints that are violated. Adding the violated constraints back into the problem, they then solve the resulting LP. They iterate this process until no local constraints are violated. The result is guaranteed to exactly match the solution to the original LP, even though only a small fraction of the original constraints are used. They observe that the number of constraints used for linear codes is only a small multiple (1.1-1.5) of the number m of parity-checks, even for codes with high check degree, and that ALP decoding is significantly, sometimes several orders of magnitude, more efficient, than standard LP decoding.
Details of Linear Programming and Adaptive Linear Programming Decoders
Suppose that the code that must be decoded is a length-n binary linear code C. Assume that a binary codeword xεC is transmitted from a source to a destination, over a memory-less communication channel. The destination receives a codeword y, which is a version of the codeword x that has been distorted by the channel. Pr[{circumflex over (x)}|y] is the probability that: a particular codeword {circumflex over (x)}εC was sent, given, that y is received. If all the codewords are equally likely to be sent, then the ML decoding problem reduces to the following problem:
                    Minimize        ⁢                                  ⁢                              ∑            i                    ⁢                                    γ              i                        ⁢                                          x                ^                            i                                                          (        1        )                                                      subject            ⁢                                                  ⁢            to            ⁢                                                  ⁢            the            ⁢                                                  ⁢            constraint            ⁢                                                  ⁢                          x              ^                                ∈          C                ,                                  ⁢                  where          ⁢                                          ⁢                      γ            i                    ⁢                                          ⁢          is          ⁢                                          ⁢          the          ⁢                                          ⁢          i          ⁢                                          ⁢          th          ⁢                                          ⁢          negative          ⁢                                          ⁢          log          ⁢                      -                    ⁢          likelihood          ⁢                                          ⁢          ratio          ⁢                                          ⁢          defined          ⁢                                          ⁢          as                                    (        2        )                                          γ          i                =                              log            ⁡                          (                                                Pr                  ⁡                                      [                                                                                            y                          i                                                |                                                  x                          i                                                                    =                      0                                        ]                                                                    Pr                  ⁡                                      [                                                                                            y                          i                                                |                                                  x                          i                                                                    =                      1                                        ]                                                              )                                .                                    (        3        )            
Here {circumflex over (x)}i is the ith symbol of the candidate codeword {circumflex over (x)}, yi is the ith symbol of the received sequence y, and xi is the ith symbol of the transmitted codeword x. For example, if the channel is a binary symmetric channel (BSC) with bit-flip probability p, then γi=log(p/(1−p)) if the received bit yi=1, and γi=log((1−p)/p) if the received bit yi=0. The appropriate negative log-likelihood ratios γi can be calculated for other channels as well.
The constraints (2) for the minimization problem (1) are binary. Feldman et al. introduced the idea of solving a relaxed version of this minimization problem in which the binary constraints of (2) are replaced by more tractable constraints over continuous variables. Specifically, the symbols {circumflex over (x)}i are allowed to take any value between and including 0 and 1. This relaxed version of the minimization problem is a linear program.
Each parity check in the code C implies a number of local linear constraints that codewords of that code must satisfy. The intersection of these constraints defines a “polytope” over which a linear programming (LP) decoder operates. The polytope has both integer and non-integer vertices. An integer vertex is one in which for all i, {circumflex over (x)}i is 0 or 1, while a non-integer vertex is one that includes {circumflex over (x)}i values that are greater than 0 and less than 1.
The integer vertices of the polytope correspond to codeword in C. When the LP optimum is at an integer vertex. Equation (2) is satisfied and the ML solution is found, even though only a relaxed version of the minimization problem was solved. However, when the LP optimum is at a non-integer vertex. Equation (2) is not satisfied and the LP solution is not the ML codeword. Such non-integer solutions are termed “pseudo codewords.”
The precise form of the parity check constraints that define the polytope used by Taghavi, et al. is as follows. First, for all bits i, {circumflex over (x)}i is continuous-valued and satisfies the inequalities0≦{circumflex over (x)}i≦1.   (4)
Then, for every check j=1, . . . , m, every configuration of the set of neighboring variables N(j) ⊂{1, 2, . . . , n} must satisfy the following parity-check inequality constraint: for all subsets Ω⊂N(j) such that |Ω| is odd,
                                                        ∑                              i                ∈                Ω                                      ⁢                                          x                ^                            i                                -                                    ∑                              i                ∈                                                      M                    ⁡                                          (                      j                      )                                                        /                  Ω                                                      ⁢                                          x                ^                            i                                      ≤                                          Ω                                -          1.                                    (        5        )            
Taghavi et al. define a violated constraint as a “cut.” The iterative ALP decoding method starts with the vertex obtained by solving a simple initial problem that only includes a small number of all the LP constraints, and iteratively adds violated constraints and re-solves until no constraints are violated. Taghavi et al. show that violated constraints can be sorted and found efficiently.
The simple initial problem consists of using only the constraints0≦{circumflex over (x)}i if γi>0,{circumflex over (x)}i≦1 if γi<0.   (6)
The optimum solution of this simple initial problem is immediately found by hard-decision decoding.
As shown in FIG. 5, the conventional ALP method operates as follows;
Initialize 510 the initial problem using the constraints in Equation (6);
Perform 520 LP decoding;
Find 530 all violated constraints of the current solution;
If one or more violated constraints are found, then add 540 the violated constraints to the problem constraints, and go to step 2 if true); and
Otherwise, if false, then the current solution, is an estimate of the final ALP codeword 541.
The ALP decoding method obtains the same codewords or pseudo codewords as standard LP decoders, the only difference is that ALP decoders consume less time.
When the solution of LP or ALP decoder is non-integer, the ML codeword has not been found, and one is motivated to find a tightening of the original LP relaxation.
One method of tightening the original LP relaxation is to introduce additional linear constraints that result from redundant parity-check equations. That approach is described by Feldman et al., “Using linear programming to decoding binary linear codes,” and Taghavi et al., “Adaptive linear programming decoding.” Not all redundant parity-check equations improve performance. Therefore, one must search for useful redundant parity-check equations. The computational load of that search, and the quality of the search results, have a large impact on the usefulness of the resulting algorithm. So far, those approaches have not yielded a useable ML decoder.
Another method enforces a set of integer constraints. That approach is described by Feldman et al, “Using linear programming to decoding binary linear codes,” and by K. Yang, J. Feldman, and X. Wang, “Nonlinear programming approaches to decoding low-density parity-check codes, IEEE J. Select, Areas Commun. 24; 1603-1613, August 2006. A mixed-integer LP solver is used, but complexity constraints keep the applicability of that method to short block-lengths. Feldman et al. only describes decoding results for a block-length, up to 60 bits, and word error rates down to only 10−4.
Another related method is the augmented BP approach, N. Varnica, M. Fossorier, and A. Kavcic, “Augmented belief-propagation decoding of low-density parity check codes,” IEEE Trans. Commun, Volume 54, Issue 10, pages 1896-1896, October 2006. They start with BP, and progressively fix the least certain bits. However, because that method uses BP, the decoder may not succeed in returning a codeword in a reasonable amount of time, and if it does return a codeword, it is not guaranteed to be the optimal ML codeword.
None of the prior-art decoding methods have provided a decoding method capable of performing optimal ML decoding of LDPC codes with long block-lengths (e.g., block-lengths greater than 100) in a reasonable amount of time, e.g., to be able to produce ML decoding results for word error rates down to 10−6 or less. Such a decoding method is strongly desired.